package list;

/**
 * 步数  fast  = 2 * slow    fast - slow = n * b （b : 环长）  =>  slow = n * b
 *
 *  入口点的步数都是  a  + n * b    因此  再来个指针  和slow一起走 a 步  相遇就是起点
 *
 *
 *  https://leetcode-cn.com/problems/linked-list-cycle-ii/submissions/
 */
public class 环形链表II_142 {
    public static ListNode detectCycle(ListNode head) {
        ListNode fast = head; ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) { // slow = n * 环长
                ListNode p = head;
                while(p != slow) { // 循环到 p = a    slow = a + n * 环长
                    p = p.next;
                    slow = slow.next;
                }
                return p;
            }
        }
        return null;
    }


    public static void main(String[] args) {
        ListNode t3 = new ListNode(3);
        ListNode s2 = new ListNode(2);
        ListNode z0 = new ListNode(0);
        ListNode f4 = new ListNode(4);
        t3.next = s2; s2.next = z0; z0.next = f4; f4.next = s2;
        detectCycle(t3);


    }
}
